package com.beimihu.lianxi;

public class DP {
    public static void packProblem(){
        int C = 5; // 背包容量
        int n = 3; // 物品数量
        int[] w = {2, 3, 1}; // 物品重量
        int[] v = {4, 5, 3}; // 物品价值

        int[][] dp = new int[n + 1][C + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= C; j++) {
                if (w[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                }
            }
        }

        System.out.println("背包能获得的最大价值是: " + dp[n][C]);
    }

}
